SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Optimistic replication</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Optimistic replication</span></span>

</h1>

</header>

<p><b>Optimistic replication</b>, also known as <b>lazy replication</b>,<sup id="cite_ref-Ladin1992_1-0" class="reference"><a href="#cite_note-Ladin1992-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Ladin1990_2-0" class="reference"><a href="#cite_note-Ladin1990-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> is a strategy for <a href="Replication_(computer_science)" class="mw-redirect" title="Replication (computer science)">replication</a>, in which replicas are allowed to diverge.<sup id="cite_ref-saito2005_3-0" class="reference"><a href="#cite_note-saito2005-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>Traditional pessimistic replication systems try to guarantee from the beginning that all of the replicas are identical to each other, as if there was only a single copy of the data all along. Optimistic replication does away with this in favor of <a href="Eventual_consistency" title="Eventual consistency">eventual consistency</a>, meaning that replicas are guaranteed to converge only when the system has been <a href="Quiesce" title="Quiesce">quiesced</a> for a period of time. As a result, there is no longer a need to wait for all of the copies to be synchronized when updating data, which helps <a href="Concurrency_(computer_science)" title="Concurrency (computer science)">concurrency</a> and <a href="Parallel_computing" title="Parallel computing">parallelism</a>. The trade-off is that different replicas may require explicit reconciliation later on, which might then prove difficult or even insoluble.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<p>An optimistic replication algorithm consists of five elements:

</p>

<ol><li><b>Operation submission</b>: Users submit operations at independent sites.</li>

<li><b>Propagation</b>: Each site shares the operations it knows about with the rest of the system.</li>

<li><b>Scheduling</b>: Each site decides on an order for the operations it knows about.</li>

<li><b>Conflict resolution</b>: If there are any conflicts among the operations a site has scheduled, it must modify them in some way.</li>

<li><b>Commitment</b>: The sites agree on a final schedule and conflict resolution result, and the operations are made permanent.</li></ol>

<p>There are two strategies for propagation: state transfer, where sites propagate a representation of the current state, and operation transfer, where sites propagate the operations that were performed (essentially, a list of instructions on how to reach the new state).

</p><p>Scheduling and conflict resolution can either be syntactic or semantic. Syntactic systems rely on general information, such as when or where an operation was submitted. Semantic systems are able to make use of application-specific information to make smarter decisions. Note that state transfer systems generally have no information about the semantics of the data being transferred, and so they have to use syntactic scheduling and conflict resolution.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>One well-known example of a system based on optimistic replication is the <a href="Concurrent_Versions_System" title="Concurrent Versions System">CVS</a> <a href="Revision_control" class="mw-redirect" title="Revision control">version control system</a>, or any other version control system which uses the <a rel="nofollow" class="external text" href="http://tortoisesvn.net/docs/release/TortoiseSVN_en/tsvn-basics-versioning.html">copy-modify-merge</a> paradigm. CVS covers each of the five elements:

</p>

<ol><li>Operation submission: Users edit local versions of files.</li>

<li>Propagation: Users manually pull updates from a central server, or push changes out once the user feels they are ready.</li>

<li>Scheduling: Operations are scheduled in the order that they are received by the central server.</li>

<li>Conflict resolution: When a user pushes to or pulls from the central repository, any conflicts will be flagged for that user to fix manually.</li>

<li>Commitment: Once the central server accepts the changes which a user pushes, they are permanently committed.</li></ol>

<p>A special case of replication is <a href="Data_synchronization" title="Data synchronization">synchronization</a>, where there are only two replicas. For example, <a href="Personal_Digital_Assistant" class="mw-redirect" title="Personal Digital Assistant">personal digital assistants (PDAs)</a> allow users to edit data either on the PDA or a computer, and then to <a href="Merge_(revision_control)" class="mw-redirect" title="Merge (revision control)">merge</a> these two datasets together. Note, however, that replication is a broader problem than synchronization, since there may be more than two replicas.

</p><p>Other examples include:

</p>

<ul><li><a href="Usenet" title="Usenet">Usenet</a>, and other systems which use the <a href="Thomas_write_rule" title="Thomas write rule">Thomas Write Rule</a> (See <a rel="nofollow" class="external text" href="http://tools.ietf.org/html/rfc677">Rfc677</a>)</li>

<li><a href="Multi-master_replication" title="Multi-master replication">Multi-master database replication</a><sup id="cite_ref-Gray1996_4-0" class="reference"><a href="#cite_note-Gray1996-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li>

<li>The <a href="Coda_(file_system)" title="Coda (file system)">Coda</a> distributed filesystem</li>

<li><a href="Operational_transformation" title="Operational transformation">Operational Transformation</a>, a theoretical framework for group editing</li>

<li><a href="Peer-to-peer_wiki" class="mw-redirect" title="Peer-to-peer wiki">Peer-to-peer wikis</a></li>

<li><a href="Conflict-free_replicated_data_type" title="Conflict-free replicated data type">Conflict-free replicated data types</a></li>

<li>The Bayou<sup id="cite_ref-Terry1995_5-0" class="reference"><a href="#cite_note-Terry1995-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> distributed database</li>

<li>IceCube<sup id="cite_ref-Kermarrec2001_6-0" class="reference"><a href="#cite_note-Kermarrec2001-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Implications">Implications</h2></div>

<p>Applications built on top of optimistic replicated databases need to be careful about ensuring that the delayed updates observed do not impair the correctness of the application.

</p><p>As a simple example, if an application contains a way of viewing some part of the database state, and a way of editing it, then users may edit that state but then not see it changing in the viewer. Alarmed that their edit "didn't work", they may try it again, potentially more than once. If the updates are not <a href="Idempotence" title="Idempotence">idempotent</a> (e.g., they increment a value), this can lead to disaster. Even if they are idempotent, the spurious database updates can lead to performance bottlenecks, especially when the database systems are processing heavy loads; this can become a vicious circle.

</p><p>Testing of applications is often done on a testing environment, smaller in size (perhaps only a single server) and less loaded than the "live" environment. The replication behaviour of such an installation may differ from a live environment in ways that mean that replication lag is unlikely to be observed in testing, masking replication-sensitive bugs. Application developers must be very careful about the assumptions they make about the effect of a database update, and must be sure to simulate lag in their testing environments.

</p><p>Optimistically replicated databases have to be very careful about offering features such as validity constraints on data. If any given update may or may not be accepted based on the current state of the record, then two updates (A and B) may be individually legal against the starting state of the system, but one or more of the updates may not be legal against the state of the system after the other update (e.g., A and B are both legal, but AB or BA are illegal). If A and B are both initiated at roughly the same time within the database, then A may be successfully applied on some nodes and B on others, but as soon as A and B "meet" and one is attempted on a node which has already applied the other, a conflict will be found. The system must, in this case, decide which update finally "wins", and arrange for any nodes that have already applied the losing update to revert it. However, some nodes may temporarily expose the state with the reverted update, and there may be no way to inform the user who initiated the update of its failure, without requiring them to wait (potentially forever) for confirmation of acceptance at every node.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLadin,_R.Liskov,_B.Shrira,_L.Ghemawat,_S.1992" class="citation journal cs1">Ladin, R.; Liskov, B.; Shrira, L.; Ghemawat, S. (1992). "Providing high availability using lazy replication". <i>ACM Transactions on Computer Systems</i>. <b>10</b> (4): <span class="nowrap">360–</span>391. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.586.7749">10.1.1.586.7749</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F138873.138877">10.1145/138873.138877</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2219840">2219840</a>.</cite></span>

</li>

<li id="cite_note-Ladin1990-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Ladin1990_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFLadin,_R.Liskov,_B.Shrira,_L.1990" class="citation conference cs1">Ladin, R.; Liskov, B.; Shrira, L. (1990). <i>Lazy replication: exploiting the semantics of distributed services</i>. Proceedings of the Ninth Annual ACM <a href="Symposium_on_Principles_of_Distributed_Computing" title="Symposium on Principles of Distributed Computing">Symposium on Principles of Distributed Computing</a>. pp. <span class="nowrap">43–</span>57. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F93385.93399">10.1145/93385.93399</a></span>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F149694">1721.1/149694</a></span>.</cite></span>

</li>

<li id="cite_note-saito2005-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-saito2005_3-0">^</a></b></span> <span class="reference-text"> <cite id="CITEREFSaitoShapiro2005" class="citation journal cs1">Saito, Yasushi; Shapiro, Marc (2005). "Optimistic replication". <i><a href="ACM_Computing_Surveys" title="ACM Computing Surveys">ACM Computing Surveys</a></i>. <b>37</b> (1): <span class="nowrap">42–</span>81. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.324.3599">10.1.1.324.3599</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1057977.1057980">10.1145/1057977.1057980</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1503367">1503367</a>.</cite> </span>

</li>

<li id="cite_note-Gray1996-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Gray1996_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFGray,_J.Helland,_P.O’Neil,_P.Shasha,_D.1996" class="citation conference cs1"><a href="Jim_Gray_(computer_scientist)" title="Jim Gray (computer scientist)">Gray, J.</a>; Helland, P.; <a href="Patrick_O'Neil" title="Patrick O'Neil">O’Neil, P.</a>; <a href="Dennis_Shasha" title="Dennis Shasha">Shasha, D.</a> (1996). <a rel="nofollow" class="external text" href="ftp://ftp.research.microsoft.com/pub/tr/tr-96-17.pdf"><i>The dangers of replication and a solution</i></a> <span class="cs1-format">(PDF)</span>. Proceedings of the 1996 <a href="ACM_SIGMOD_International_Conference_on_Management_of_Data" class="mw-redirect" title="ACM SIGMOD International Conference on Management of Data">ACM SIGMOD International Conference on Management of Data</a>. pp. <span class="nowrap">173–</span>182. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F233269.233330">10.1145/233269.233330</a>.</cite></span>

</li>

<li id="cite_note-Terry1995-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Terry1995_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFTerry,_D.B.Theimer,_M.M.Petersen,_K.Demers,_A.J.1995" class="citation conference cs1">Terry, D.B.; Theimer, M.M.; Petersen, K.; Demers, A.J.; Spreitzer, M.J.; Hauser, C.H. (1995). <i>Managing update conflicts in Bayou, a weakly connected replicated storage system</i>. Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles. pp. <span class="nowrap">172–</span>182. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F224056.224070">10.1145/224056.224070</a></span>.</cite></span>

</li>

<li id="cite_note-Kermarrec2001-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Kermarrec2001_6-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKermarrec,_A.M.Rowstron,_A.Shapiro,_M.Druschel,_P.2001" class="citation conference cs1">Kermarrec, A.M.; Rowstron, A.; Shapiro, M.; Druschel, P. (2001). <i>The IceCube approach to the reconciliation of divergent replicas</i>. Proceedings of the Twentieth Annual ACM <a href="Symposium_on_Principles_of_Distributed_Computing" title="Symposium on Principles of Distributed Computing">Symposium on Principles of Distributed Computing</a>. pp. <span class="nowrap">210–</span>218. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F383962.384020">10.1145/383962.384020</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite id="CITEREFSaitoShapiro2003" class="citation web cs1">Saito, Yasushi; Shapiro, Marc (September 2003). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2003-60.pdf">"Optimistic Replication"</a> <span class="cs1-format">(PDF)</span>. Microsoft.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-11" href="https://en.wikipedia.org/wiki/?title=Optimistic_replication&oldid=1256728557">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>